本场链接:Codeforces Round #651

A. Maximum GCD

题目大意:给定一个正整数$n$,找到两个数$a,b$满足$1 \leq a \le b \leq n$,且gcd(a,b)$最大,输出最终的值即可(不需要输出$a,b$具体是多少,只需要gcd的值).
数据范围:
$2 \leq n \leq 10^6$

枚举若干个数可以发现,如果$n$是奇数,则应该是前面的$n-1$和$(n-1) / 2$的gcd作为答案,因为奇数至少也要除$3$,必然比偶数的小.偶数同理.最终结果就是$n/2$

B. GCD Compression

题目大意:有一个长度为$2n$的序列,现在想把他压缩到$n-1$长度的序列$b$.按如下操作方式压缩:首先任意丢掉$a$里的两个元素,之后任取两个$a$中的元素,删掉他们俩,再把他们俩的和加入$b$.注意第一次是直接丢掉的.要求$b$整个序列的gcd大于$1$,即$gcd(b_1,b_2,...b_{n-1}) > 1$.
数据范围:
$2 \leq n \leq 2000$
$1 \leq a_i \leq 1000$

显然正面直接构造相当困难,选择太多了.注意到题目的数据非常小,$b_i \leq 2000$,由于$gcd(b_1,b_2,...b_{n-1}) > 1$这个条件,我们可以得到一个重要条件:即整个$b$序列是有一个比$1$大的公共因数的,并且由于所有的数都比$2000$小,所以可以直接枚举这个因数具体是谁,按余数对$a$进行分类.如果有一组的个数是奇数,那么就要把这一组里的一个数删掉(对应题目开始时的操作),因为是两两相组,所以奇数必然会剩下一个.最多可以删$2$次.
最后看是不是满足条件的就可以了.不过还需要注意:第一步是不能不做的,如果不符合条件的恰好只有一个,那么删去就行了,如果一个都没有,你也不能不删,随便挑一个删去就可以了.对应到代码里就是到最后发现$ok=3$,过多了,需要多删一组.
其次,容易想到这个公共的因子肯定得是一个质数,如果是合数其实是没意义的,进一步可以降低复杂度.从小到大依次枚举每个质数,再进行分类,就可以做掉这道题了.(是不是直接枚举因数就可以过掉我也没试过,可以自己尝试一下)
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1005;
int primes[N],st[N],cnt;
vector<int> edges[N];
void init()
{
	for(int i = 2;i < N;++i)
	{
		if(!st[i])	primes[cnt++] = i;
		for(int j = 0;i * primes[j] < N;++j)
		{
			st[primes[j] * i] = 1;
			if(i % primes[j] == 0)	break;	
		}
	}
}
int main()
{
	init();
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);n *= 2;
		vector<int> a(n + 17,0);
		for(int i = 0;i < n;++i)	scanf("%d",&a[i]);
    	if(n == 4)
    	{
    		printf("3 4\n");
    		continue;
    	}
    	for(int i = 0;i < cnt;++i)
    	{
    		int ok = 3;
    		int div = primes[i];
    		for(int j = 0;j < div;++j)	edges[j].clear();
    		for(int j = 0;j < n;++j)
    			edges[a[j] % div].push_back(j);
    		vector<pii> res;
    		for(int j = 0;j < div;++j)
    		{
    			if(edges[j].size() % 2)
    			{
    				if(ok)
    				{
    					--ok;
    					edges[j].pop_back();
    				}
					else	break;
    			}
    			for(int k = 0;k < edges[j].size();k += 2)
    				res.push_back({edges[j][k] + 1,edges[j][k + 1] + 1});
    		}
    		if(ok)
    		{
    			for(auto& v : res)
    			{
    				if(ok > 2)
    				{
    					--ok;
    					continue;
    				}
    				printf("%d %d\n",v.first,v.second);
    			}
    			break;
    		}
    	}
    }
    return 0;
}

C. Number Game

题目大意:两个人在玩一个游戏,一开始有一个正整数$n$,每一次可以除掉$n$的一个奇因子.或者减一.当$n=1$的时候上述操作都不能进行.先不能采取任何行动的玩家输,问是否是先手必胜的.
注意:奇因子是包含$n$自己的.
数据范围:
$1 \leq n \leq 10^9$

显然,除了$1$之外的所有奇数都是先手必胜的.现在的问题就是偶数是怎样判明的:观察样例可以发现肯定不是直接跟偶数相关的,可能跟其内有几个偶数几个奇数有关.考虑把偶数变成一个更数学化的形式:对于一个偶数$x$,他可以表示成若干个奇质数乘积和一个$2$的幂的乘积形式,即$x=p1*p2*p3......*2^n$其中$p$全是奇质数,不包含$2$.由于说奇数是必胜状态,这个问题的转化方向肯定是和$2$的幂$n$具体是多少有关,一个一个来考虑一下试试:
首先,如果$n=1$,即原来的数$x$里只有一个$2$存在的话:
①他就是$2$,没有一个奇因子$p$,显然是必胜的.
②至少有一个奇因子存在,这个时候可以把所有的奇因子全部除掉,就剩下一个$2$,而$2$显然是一个必胜状态,这样就必败了.所以这个时候还要考虑的是$p$有几个,因为如果$p$只有一个的话,无论是减一也好还是除掉奇因子也好,必然会给$2$这个数或者是一个奇数(因为偶数减一必然是奇数)让给对手,就必败了.如果$p$有多个的话,那么我只要留下一个$p$这个状态给对手,对手显然就是一个必败状态,而我是一个必胜状态了.因为之前说了如果手上只有一个奇因子$p$,一定会把必胜状态给对手,导致必败.
综上,如果没有奇因子,则必胜,如果只有一个,则必败,如果有一个以上,则必胜.
当然,对于这种情况,如果没有奇因子的时候就是单纯的$2$,在去掉这个$2$之后如果还是一个质数的话,则对应只有一个奇因子,必败.反之是一个合数,表示有多个奇因子,必胜.可能要稍微好写一点.
其次,如果有多个$2$,即$n>1$的话,情况又会有变:
①假设手上就是一个$2^n$,没有奇因子,只能执行$-1$操作给对手一个奇数,导致必败.
②如果手上只有一个奇因子$p$的话,肯定不会去减一,减一相当于直接送分.去掉一个奇因子的话,剩下的一个$2^n$到对手手上,只能是$-1$操作,得到一个奇数再还回来,因此必胜.
③如果有多个奇因子同②.
综上,如果没有奇因子,必败,如果有则必胜.
对上述两种情况分别讨论即可.
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int primes[N],st[N],cnt;
bool isprime(int x)
{
	for(int i = 2;i <= x / i;++i)
		if(x % i == 0)	
			return 0;
	return 1;
}
void lose()
{
	puts("FastestFinger");
}
void win()
{
	puts("Ashishgup");
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
    	int n;scanf("%d",&n);
    	// cout << (n / 2) << endl;
    	if(n == 1)	lose();
    	else if(n == 2)	win();
    	else if(n % 2)	win();
		else 
		{
			// cout << contain << endl;
			if(n % 4 == 0)
			{
				while(n % 2 == 0)	n /= 2;
				if(n == 1)	lose();
				else win();
			}
			else
			{
				n /= 2;
				if(isprime(n))	lose();
				else win();
			}
		}
    }
    return 0;
}

D. Odd-Even Subsequence

题目大意:有一个长度为$n$的序列$a$,找到$a$的一个子序列$b$,他的长度为$k$,使这个子序列$b$的偶数位置上的最大值和奇数位置上的最大值两者的最小值最小.输出这个最小值即可,不需要输出具体方案.
定义子序列是删去序列里若干个元素,但不改变剩余元素的相对位置得到的序列.
注意,是$b$里的奇数位置和偶数位置,不是这个元素之前在$a$里的位置.

数据范围:
$2 \leq k \leq n \leq 2*10^5$
$1 \leq a_i \leq 10^9$

这题乍看上去也是挺牛逼的,没啥想法.不过可以注意到,最终的答案表达式是两边最大值的最小值,既然如此,突破口可能就是在这里,因为这个最小值意味着我可以让一边很大但是一边很小,反正答案是取得最小值,我另一边取的再大都没问题.
如果把这些条件都去掉的话,可以发现这就是一个二分答案的题:首先确定一个答案表示整个序列里的最大值最多是多少,判断就是看整个序列最少有几个,长度如果达到$k$就说明当前这个答案是可以构造出来的.带到本题里可以发现正确性是比较接近的,但是由于有些条件暂时没联系起来可能有问题,顺着往下想:
确定一个答案之后,在这道题里,检测一个答案是否是可以构造的,应该要有两种:一次是奇数上的,一次是偶数上的.为什么要这样做,之前也解释过了,因为答案是两者中的最小值,所以另一边无论怎样大或者小都是无所谓的,我只要管一边就行了.
做两个$check$的目的就是把两种情况都找出来,只要有一个就说明这个答案是可行的,答案还可以继续缩小.具体实现$check$的方式就是遍历,对于找奇数位置的$check$来说,偶数位置直接加进去(长度$+1$),奇数位置看是不是小于当前答案的,如果是就长度增加.直接套一个二分框架这个题就做出来了.
注意在实现$check$的时候,如果说当前的位置是需要判断大小来看是否能填入序列的,那么只有在填入了一个数的情况下状态才能改变,因为如果你没填的话这个状态变了就不对了,因为位置是在$b$里的位置而不是$a$里的位置,这一点需要注意一下.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
const int N = 2e5+7;
int a[N];
bool check(int x,bool islf)
{
	int fres = 0;
	for(int i = 1;i <= n;++i)
	{
		if(islf)
		{
			if(a[i] <= x)
			{
				++fres;
				islf = 0;
			}
		}
		else
		{
			++fres;
			islf = 1;
		}
	}
	return fres >= k;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
    int l = 0,r = 1e9,res;
    while(l < r)
    {
    	int mid = l + r >> 1;
    	if(check(mid,0) || check(mid,1))	r = mid;
    	else l = mid + 1;
    }
    printf("%d",l);
    return 0;
}

E. Binary Subsequence Rotation

题目大意:给两个二进制串$s$和$t$,规定一种操作:每次操作中你可以任取几个位置,把这几个位置$s$里的元素挑出来,往右循环旋转一次(即往右移动一格,最后一个变成开头的),再把新的几个元素按顺序填回去.问最少要几次这样的操作使$s$变成$t$.只输出次数,不输出具体方案,如果问题无解则输出$-1$.

数据范围:
$1 \leq n \leq 10^6$

显然当两个串的字符数量不对等的时候问题无解.
其次由于整个序列里旋转的位置是可以随便选的,所以如果已经相同的一对位置是毫无意义的,可以直接删掉,我们只用考虑上下不同的对.很显然这样的对只有两种,要么是$01$,要么是$10$.其次考虑至少要多少次.可以发现如果是一段$01 || 10 || 01 || 10$的串,只要循环旋转一次就够了,也就是这样的交替序列只需要操作一次.这里用两个计数变量,一个$f_0$表示以$10$为结尾的有几个,另一个$f_1$表示以$01$结尾的串有多少个.遍历所有不同对,如果是$10$形式的,就看有没有$01$的串在前面,如果有,则$--f0$并$++f1$,如果没有一个$01$的串在前面的话,就说明现在只能多开一个序列了直接$++f1$即可,另外一种情况对称处理即可.显然答案就是$f0+f1$.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
char a[N],b[N];
int s[N];
int n,m;
int main()
{
	scanf("%d",&n);
    scanf("%s",a + 1);getchar();
    scanf("%s",b + 1);
    int x0 = 0,x1 = 0;
    for(int i = 1;i <= n;++i)
    {
    	if(a[i] == b[i])	continue;
    	s[++m] = a[i] - '0';
    	if(a[i] == '1')	++x1;
    	else ++x0;
    }
    if(x1 != x0)
    {
    	puts("-1");
    	return 0;
    }
    if(!m)	puts("0");
    else
    {
    	int res = 0;
    	int f1 = 0,f0 = 0;
    	for(int i = 1;i <= m;++i)
    	{
    		if(s[i] == 1)
    		{
    			if(f0)	--f0,++f1;
    			else ++f1;
    		}
    		else
    		{
    			if(f1)	--f1,++f0;
    			else ++f0;
    		}
    	}
    	printf("%d",f0 + f1);
    }
    return 0;
}